Regular expressions can be used to provide a concise and formal way of describing a set of strings over an alphabet. A regular expression matches a string if the string belongs to the set described by the regular expression. Regular expression matching may be used, for example, by command shells, programming languages, text editors, and search engines to search for text within a document. Regular expressions can include word boundary symbols that match boundaries between word and non-word characters. The worst-case matching times of known techniques for checking whether an input string matches a regular expression with word boundary symbols can be exponential in the length of the input string.